%!TEX options=--shell-escape
\documentclass{beamer}
\usetheme{Madrid}
\usepackage{minted}
\usepackage{multicol}
\usepackage{environ}

\newcommand{\nth}{\ensuremath{^\text{th}}}
\newcommand{\bigo}[1]{\ensuremath{\text{O}(#1)}}
\def\CC{{C\nolinebreak[4]\hspace{-.05em}\raisebox{.4ex}{\tiny\bf ++}}}

 \newenvironment{bigoexample}[1]
 {\def\tempvar{#1}\frametitle{E.g.}What is the Big-O of the following function?\VerbatimEnvironment
  \begin{minted}{python}}
 {\end{minted}\onslide<2->{\textit{Answer:} \tempvar}}
 % {\end{minted}\only<2>{Answer: \bigo{\tempvar}}}

\AtBeginSection[]{
  \begin{frame}
    \frametitle{Table of Contents}
    \tableofcontents[currentsection]
  \end{frame}
}

\title{Introduction and Big-O notation}% \subtitle{foobar}
\author[B. Rudner]{Bronson Rudner}
\institute[]{South African Programming Olympiad \\ Training Camp}
\date{December 12, 2020}% \titlegraphic{\includegraphics[height=2cm]{logo}}

\begin{document}
\frame{\titlepage}

% \begin{frame}
% \frametitle{Table of Contents}
% \tableofcontents
% \end{frame}

\begin{frame}
\frametitle{What do I need to know to solve programming problems?}
\begin{itemize}
 \item<2-> Basic coding skills and fluency
 \item<3-> Knowledge of algorithms and data structures
 \item<4-> Ability to problem solve
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Todays agenda}
We are focusing on algorithms and data structures. Why?
\begin{itemize}
 \item<2-> Learning to code these will ensure you develop your basic coding skills
 and fluency
 \item<3-> Many problems reduce to one of, or some subset of these
 \item<4-> They provide inspiration for further solutions
 \item<5-> Serve as a guideline for solving problems efficiently
 % \item Serve as a guideline for how efficiently a problem can be solved
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Types of problems in programming contests}
\begin{multicols}{2}
\begin{enumerate}
\item Ad-Hoc
\item Greedy
\item Computational Geometry
\item Dynamic Programming
\item BigNums
\item Two-Dimensional
\item Eulerian Path
\item Minimum Spanning Tree
\item Knapsack
\item Network Flow
\item Flood Fill
\item Shortest Path
\item Approximate Search
\item Complete Search
\item Recursive Search Techniques
\item Heuristic Search
\end{enumerate}
\end{multicols}
\end{frame}

% Big-O

\begin{frame}
\frametitle{How fast are computers?}
\begin{itemize}
 \item<1-> Computers are fast - but their speed is still finite
 \item<2-> On the order of $100\,000\,000$ operations per second (\CC)
 \item<3-> Java about 2x slower, Python about 10x slower (and Scratch is about 100x slower)
 \item<4-> It isn't enough to find an algorithm that solves a problem
 \item<5-> It needs to solve it within the time limit
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{E.g.}
\begin{itemize}
 \item<1-> The Fibonacci series is given by $$1, 1, 2, 3, 5, 8, \mathellipsis$$
 where the next number in the sequence is given by the sum of the two preceding numbers
 \item<2-> Find the $n\nth$ Fibonacci number, given that $1\leq n\leq 1\,000$
 \item<3-> \begin{minted}{Python}
def slow_fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return slow_fibonacci(n-1) + slow_fibonacci(n-2)
\end{minted}
 \item<4-> Increasing $n$ by 1, (roughly) doubles the total number of calls of \texttt{slow\_fibonacci}.
 \item<5-> $n=40$ calls \texttt{slow\_fibonacci} about $200\,000\,000$ times!
\end{itemize}
\end{frame}
%TODO fibonacci_slow diagram

\begin{frame}[fragile]
\frametitle{Big-O notation}
\begin{itemize}
\item<1-> Gives a rough idea of the runtime of a program / function
\item<2-> Is expressed in relation to the size of the input ($n$).
\item<3-> If a program is $\bigo{f(n)}$, we mean it takes no more than $C\cdot f(n)$ steps in total, for suitably large $n$ (for some constant $C$).
\item<4-> In particular, if a program takes $T(n)$ steps, it is \bigo{T(n)}.
% \item<4-> Is an upper bound: $n=\bigo{n^2}$
% \item<5-> We ignore constant factors: $3n^2=\bigo{n^2}$
% \item<6-> We only care about the largest term: $n^2 + n=\bigo{n^2}$ (notice $n^2 + n = \bigo{n^2} + \bigo{n^2} = \bigo{2n^2} = \bigo{n^2}$)
% \item<7-> We usually consider the worst case bound
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Big-O notation}
It is an upper bound: $$n=\bigo{n^2},\quad n^2 = \bigo{n^2},\quad 1 = \bigo{n}$$
\onslide<2->{We ignore constant factors: $$3n^2=\bigo{n^2},\quad \frac{1}{2} n = \bigo{n}$$}
\onslide<3->{We only care about the largest term: $$n^2 + n=\bigo{n^2},\quad 2n^2 + 3n+1000 = \bigo{n^2}$$}
\end{frame}

\begin{frame}
\frametitle{Big-O notation}
\begin{itemize}
\item<1-> We usually consider the worst case bound
\begin{itemize}
\item E.g. linear search can be \bigo{1} in the best case, but in the worst
case, and on average, it is \bigo{n}
\end{itemize}
\item<2-> If you are sure the data is suitably random, you could use average time bound
\item<3-> Can also describe memory of a program - but usually you are given
more memory than the time bound anyway
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\begin{bigoexample}{\bigo{n^2}}
def triangular_nums(n):
    nums = []
    for i in range(n):
        num = 0
        for j in range(i+1):
            num += j+1
        nums.append(num)
    return nums
\end{bigoexample}
\end{frame}

\begin{frame}[fragile]
\begin{bigoexample}{\bigo{\sqrt{n}}}
def is_prime(n):
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True
\end{bigoexample}
\end{frame}

\begin{frame}[fragile]
\begin{bigoexample}{\bigo{nm} (where $n$, $m$ is the size of \texttt{nums1, nums2}, respectively)}
def foo(nums1, nums2):
    total = 0
    for x in nums1:
        total += x
    for x in nums1:
        for y in nums2:
            total += x * y
    return total
\end{bigoexample}
\end{frame}

\begin{frame}[fragile]
\begin{bigoexample}{\bigo{\log n}\\($\log 2^x = x$ (base 2))}
def sum_powers_of_two(n):
    total = 0
    i = 1
    while i < n:
        total += i
        i *= 2
    return total
\end{bigoexample}
\end{frame}

% (a tighter bound is \bigo{1.618^n})
\begin{frame}[fragile]
\begin{bigoexample}{\bigo{2^n} \\
% \onslide<3->{For large $n$ you require BigInts, so then actually \bigo{2^n n}}\\
\onslide<3->{(can be tightened to \bigo{1.618^n})}}
def slow_fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return slow_fibonacci(n-1) + slow_fibonacci(n-2)
\end{bigoexample}
\end{frame}

\begin{frame}[fragile]
\begin{bigoexample}{\bigo{n} (where $n$ is the number of nodes in the tree)}
def sum_values_in_binary_tree(node):
    sum = node.value
    if node.left is not None:
        sum += sum_values_in_binary_tree(node.left)
    if node.right is not None:
        sum += sum_values_in_binary_tree(node.right)
    return sum
\end{bigoexample}
\end{frame}

% \begin{frame}[fragile]
% \begin{bigoexample}{\bigo{\log n}}
% def loop_sum_powers_of_two(n):
%     total = 0
%     for i in range(n):
%         total += sum_powers_of_two(i)
%     return total
% \end{bigoexample}
% \end{frame}

\begin{frame}
\frametitle{Will my program run in time?}
Follow this procedure:
\begin{itemize}
\item<2-> Determine the Big-O of your algorithm. E.g. $\bigo{nk\log n}$.
\item<3-> Plug in the constraints of the question. E.g. $n\leq 10\,000, k\leq 50$.
Then $nk\log n \approx (10\,000)(50)(13)=6\,500\,000$
\item<4->
Your result should be reasonable amount less than $100\,000\,000$ - typically
less than $10\,000\,000$ is reasonable. You may multiply this $10\,000\,000$ by
the time limit in seconds.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Common classes of Big-O}
\renewcommand{\arraystretch}{1.25}
\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
Class & Big-O & Typical upper limit on $n$ & $n=1\,000\,000$ \\
\hline
Constant & $1$ & & $~1$ \\
Logarithmic & $\log n$ & & $~20$ \\
Square root & $\sqrt{n}$ & $10^{13}$ & $~1000$ \\
Linear & $n$ & $5\,000\,000$ & \\
Linearithmic & $n\log n$ & $200\,000$ & \\
Quadratic & $n^2$ & $5\,000$ & \\
Cubic & $n^3$ & $200$ & \\
Exponential & $2^n$ & $24$ & \\
Factorial & $n!$ & $11$ & \\
\hline
\end{tabular}
\end{center}
\end{frame}

\end{document}